package com.hqq.exercise.array;

/**
 * FindNumberMoreThanHalf 找出数组中出现次数超过一半的数字
 * 题目描述:
 * 数组中有一个数字出现次数【超过 不会等于】数组长度的一半，请找出这个数字。
 * 样例输入:
 * {1,2,3,2,2,2,5,4,2}
 * 样例输出:
 * 2
 * Created by heqianqian on 2017/8/15.
 */
public class FindNumberMoreThanHalf {


    /**
     * 基于快排算法
     */
    public static int findNumberBySort(int[] array) {
        if (array == null || array.length == 0) {
            return -1;
        }
        //获取第一轮排序后 排序好元素的最终下标
        int resultIndex = partition(array, 0, array.length - 1);
        //中位数下标
        int middleIndex = array.length / 2;
        while (resultIndex != middleIndex) {//一直循环到找到中位数
            if (resultIndex < middleIndex) {//比中位数小
                resultIndex = partition(array, resultIndex + 1, array.length - 1);
            } else {//比中位数大
                resultIndex = partition(array, 0, resultIndex - 1);
            }
        }

        //检查中位数元素出现次数是否满足数组长度的一半
        if (checkNumCount(array, array[resultIndex])) {
            return array[resultIndex];
        } else {
            return -1;
        }
    }

    /**
     * 根据超过一半的元素所出现的次数一定大于其他元素出现次数的和
     */
    public static int findNumberByCount(int[] array) {
        if (array == null || array.length == 0) {
            return -1;
        }
        int result = array[0];
        int count = 1;
        for (int i = 1; i < array.length; i++) {
            if (count == 0) {//如果count为0 则把result设置为当前元素 count设置为1
                result = array[i];
                count = 1;
            } else if (array[i] == result) {//如果当前元素和result相同 count+1
                count++;
            } else {
                count--;
            }
        }
        if (checkNumCount(array,result)){
            return result;
        }else{
            return -1;
        }
    }


    /**
     * 检查元素是否在数组中出现次数超过一半
     *
     * @param array  数组
     * @param result 目标元素
     * @return true/false
     */
    private static boolean checkNumCount(int[] array, int result) {
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == result) {
                count++;
            }
        }
        return count >= array.length / 2;
    }

    /**
     * 双指针快排
     */
    private static int partition(int[] array, int start, int end) {
        if (start >= end) {
            return -1;
        }
        int base = array[start];
        int leftIndex = start;
        int rightIndex = end;
        while (leftIndex != rightIndex) {
            while (leftIndex < rightIndex && array[rightIndex] >= base) {
                rightIndex--;
            }
            while (leftIndex < rightIndex && array[leftIndex] <= base) {
                leftIndex++;
            }
            if (leftIndex < rightIndex) {
                int temp = array[leftIndex];
                array[leftIndex] = array[rightIndex];
                array[rightIndex] = temp;
            }
        }

        array[start] = array[leftIndex];
        array[leftIndex] = base;

        return leftIndex;
    }

}
